﻿//void MergeSortNonR(int* a, int n) {
//	int* tmp = (int*)malloc(sizeof(int) * n);
//	if (tmp == NULL) {
//		perror("malloc fail");
//		return;
//	}
//	//可将gap理解为预排序元素的个数，即区间元素的个数为gap
//	int gap = 1;
//	while (gap < n) {
//		for (int i = 0; i < n; i += 2 * gap) {
//			//begin1和end1理解为在gap区间内的元素
//			int begin1 = i, end1 = i + gap - 1;
//			//begin2和end2可理解为在预排序gap区间的后面的元素
//			int begin2 = i + gap, end2 = i + 2 * gap - 1;
//			int index = i;
//			if (begin2 >= n) {
//				break;
//			}
//			if (end2 >= n) {
//				end2 = n - 1;
//			}
//			//以下的归并排都是在[begin1,end1]和[begin2,end2]进行的，将两区间进行合并
//			while (begin1 <= end1 && begin2 <= end2) {
//				if (a[begin1] < a[begin2]) {
//					tmp[index++] = a[begin1++];
//				}
//				else {
//					tmp[index++] = a[begin2++];
//				}
//			}
//			while (begin1 <= end1) {
//				tmp[index++] = a[begin1++];
//			}
//			while (begin2 <= end2) {
//				tmp[index++] = a[begin2++];
//			}
//			// 拷贝回原数组
//			//memcpy(a, tmp, index * sizeof(int));//此种也可以，但效率不高
//			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
//		}
//		gap *= 2;
//	}
//	free(tmp);
//}

//计数算法
//void CountSort(int* a, int n)
//{
//	int min = a[0], max = a[0];
//	for (size_t i = 0; i < n; i++)
//	{
//		if (a[i] < min)
//			min = a[i];
//
//		if (a[i] > max)
//			max = a[i];
//	}
//	int range = max - min + 1;
//	int* count = (int*)malloc(sizeof(int) * range);
//	printf("range:%d\n", range);
//	if (count == NULL)
//	{
//		perror("malloc fail");
//		return;
//	}
//	memset(count, 0, sizeof(int) * range);
//	// 统计数据出现次数
//	for (int i = 0; i < n; i++)
//	{
//		count[a[i] - min]++;
//	}
//	// 排序
//	int j = 0;
//	for (int i = 0; i < range; i++)
//	{
//		while (count[i]--)
//		{
//			a[j++] = i + min;
//		}
//	}
//}